//------------------------------------------------------------------------
template<typename T> csINLINE
csLinkList<T>::csLinkList()
:m_head(csNEW Node())
,m_size(0)
{
	m_head->m_next	= m_head;
	m_head->m_prev	= m_head;
}

//------------------------------------------------------------------------
template<typename T> csINLINE
csLinkList<T>::csLinkList(const csLinkList<T>& list)
:m_head(csNEW Node())
,m_size(0)
{
	m_head->m_next	= m_head;
	m_head->m_prev	= m_head;
	_assign(list.begin(),list.end());
}

//------------------------------------------------------------------------
template<typename T> csINLINE
csLinkList<T>::~csLinkList()
{
	clear();
	csSAFE_DELETE(m_head);
}

//------------------------------------------------------------------------
template<typename T> csINLINE void
csLinkList<T>::operator =(const csLinkList<T>& list)
{
	clear();
	_assign(list.begin(),list.end());
}

//------------------------------------------------------------------------
template<typename T> csINLINE bool
csLinkList<T>::operator==(const csLinkList<T>& rhs) const
{
	csASSERT((m_head==rhs.m_head&&m_size==rhs.m_size)||(m_head!=rhs.m_head));
	if(m_head==rhs.m_head)
	{
		return true;
	}
	if(m_size!=rhs.m_size)
	{
		return false;
	}
	for(const_iterator lit=begin(), rit=rhs.begin();lit==end()||rit==rhs.end();++lit,++rit)
	{
		if(*lit!=*rit)
		{
			return false;
		}
	}
	return true;
}

//------------------------------------------------------------------------
template<typename T> csINLINE bool
csLinkList<T>::operator!=(const csLinkList<T>& rhs) const
{
	csASSERT((m_head==rhs.m_head&&m_size==rhs.m_size)||(m_head!=rhs.m_head));
	return !operator==(rhs);
}

//------------------------------------------------------------------------
template<typename T> csINLINE T&
csLinkList<T>::front()
{
	csASSERT(m_head!=m_head->m_next);
	return m_head->m_next->m_data;
}

//------------------------------------------------------------------------
template<typename T> csINLINE const T&
csLinkList<T>::front() const
{
	csASSERT(m_head!=m_head->m_next);
	return m_head->m_next->m_data;
}

//------------------------------------------------------------------------
template<typename T> csINLINE T&
csLinkList<T>::back()
{
	csASSERT(m_head!=m_head->m_prev);
	return m_head->m_prev->m_data;
}

//------------------------------------------------------------------------
template<typename T> csINLINE const T&
csLinkList<T>::back() const
{
	csASSERT(m_head!=m_head->m_prev);
	return m_head->m_prev->m_data;
}

//------------------------------------------------------------------------
template<typename T> csINLINE void
csLinkList<T>::push_back(const T& val)
{
	insert(end(),val);
}

//------------------------------------------------------------------------
template<typename T> csINLINE void
csLinkList<T>::pop_back()
{
	csASSERT(m_size>0);
	iterator it(--end());
	remove(it);
}

//------------------------------------------------------------------------
template<typename T> csINLINE void
csLinkList<T>::push_front(const T& val)
{
	insert(begin(),val);
}

//------------------------------------------------------------------------
template<typename T> csINLINE void
csLinkList<T>::pop_front()
{
	csASSERT(m_size>0);
	remove(begin());
}

//------------------------------------------------------------------------
template<typename T> csINLINE typename csLinkList<T>::iterator
csLinkList<T>::begin()
{
	return iterator(m_head->m_next);
}

//------------------------------------------------------------------------
template<typename T> csINLINE typename csLinkList<T>::const_iterator
csLinkList<T>::begin() const
{
	return const_iterator(m_head->m_next);
}

//------------------------------------------------------------------------
template<typename T> csINLINE typename csLinkList<T>::iterator
csLinkList<T>::end()
{
	return iterator(m_head);
}

//------------------------------------------------------------------------
template<typename T> csINLINE typename csLinkList<T>::const_iterator
csLinkList<T>::end() const
{
	return const_iterator(m_head);
}

//------------------------------------------------------------------------
template<typename T> csINLINE typename csLinkList<T>::reverse_iterator
csLinkList<T>::rbegin()
{
	return reverse_iterator(m_head->m_prev);
}

//------------------------------------------------------------------------
template<typename T> csINLINE typename csLinkList<T>::const_reverse_iterator
csLinkList<T>::rbegin() const
{
	return const_reverse_iterator(m_head->m_prev);
}

//------------------------------------------------------------------------
template<typename T> csINLINE typename csLinkList<T>::reverse_iterator
csLinkList<T>::rend()
{
	return reverse_iterator(m_head);
}

//------------------------------------------------------------------------
template<typename T> csINLINE typename csLinkList<T>::const_reverse_iterator
csLinkList<T>::rend() const
{
	return const_reverse_iterator(m_head);
}

//------------------------------------------------------------------------
template<typename T> csINLINE typename csLinkList<T>::iterator
csLinkList<T>::insert(typename csLinkList<T>::iterator where, const T& val)
{
	Node* node		= csNEW Node(val);
	node->m_next	= where.m_node;
	node->m_prev	= where.m_node->m_prev;
	node->m_next->m_prev	= node;
	node->m_prev->m_next	= node;
	++m_size;
	return iterator(node);
}

//------------------------------------------------------------------------
template<typename T> csINLINE void
csLinkList<T>::remove(typename csLinkList<T>::iterator where)
{
	csASSERT(where.m_node&&where!=end());
	Node* node	= where.m_node;
	node->m_prev->m_next	= node->m_next;
	node->m_next->m_prev	= node->m_prev;
	csDELETE node;
	--m_size;
}

//------------------------------------------------------------------------
template<typename T> csINLINE typename csLinkList<T>::iterator
csLinkList<T>::remove_return_next(typename csLinkList<T>::iterator where)
{
	csASSERT(where.m_node&&where!=end());
	iterator cur(where.m_node->m_next);
	remove(where);
	return cur;
}

//------------------------------------------------------------------------
template<typename T> csINLINE void
csLinkList<T>::remove(const T& val)
{
	iterator it(find(val));
	while(it!=end())
	{
		iterator tit = it;
		it = find(val,it);
		remove(tit);
	}
}


//------------------------------------------------------------------------
template<typename T> csINLINE typename csLinkList<T>::iterator
csLinkList<T>::find(const T& val)
{
	return find(val,end());
}

//------------------------------------------------------------------------
template<typename T> csINLINE typename csLinkList<T>::const_iterator
csLinkList<T>::find(const T& val) const
{
	return find(val,end());
}

//------------------------------------------------------------------------
template<typename T> csINLINE typename csLinkList<T>::iterator
csLinkList<T>::find(const T& val, typename csLinkList<T>::iterator it)
{
	++it;
	iterator iend = end();
	while(it!=iend)
	{
		if(it.m_node->m_data==val)
		{
			return it;
		}
		++it;
	}
	return end();
}

//------------------------------------------------------------------------
template<typename T> csINLINE typename csLinkList<T>::const_iterator
csLinkList<T>::find(const T& val, typename csLinkList<T>::const_iterator it) const
{
	++it;
	const_iterator iend = end();
	while(it!=iend)
	{
		if(it.m_node->m_data==val)
		{
			return it;
		}
		++it;
	}
	return end();
}

//------------------------------------------------------------------------
template<typename T> csINLINE bool
csLinkList<T>::empty() const
{
	return 0==m_size;
}

//------------------------------------------------------------------------
template<typename T> csINLINE s32
csLinkList<T>::size() const
{
	return m_size;
}

//------------------------------------------------------------------------
template<typename T> void
csLinkList<T>::clear()
{
	iterator it = begin();
	iterator iend= end();
	while(it!=iend)
	{
		it = remove_return_next(it);
	}
}

//------------------------------------------------------------------------
template<typename T> csINLINE void
csLinkList<T>::swap(csLinkList<T>& rhs)
{
	csSwap<Node*>(m_head,rhs.m_head);
	csSwap<s32>(m_size,rhs.m_size);
}

//------------------------------------------------------------------------
template<typename T> void
csLinkList<T>::to_array(T** outArray) const
{
	csASSERT(csNULL!=outArray);
	const_iterator it	= begin();
	const_iterator iend	= end();
	s32	i			= 0;
	while(it!=iend)
	{
		(*outArray)[i] = *it;
		++it;
		++i;
	}
}

//------------------------------------------------------------------------
template<typename T> void
csLinkList<T>::_assign(typename csLinkList<T>::const_iterator beginNode, typename csLinkList<T>::const_iterator endNode)
{
	clear();
	for(const_iterator it=beginNode;it!=endNode;++it)
	{
		push_back(it.m_node->m_data);
	}
}
